Prefiksufiks
Limit pamięci: 64 MB
W tym zadaniu będą nas interesować napisy złożone z małych liter alfabetu angielskiego.
Prefiksem danego napisu nazwiemy dowolny jego początkowy fragment.
Sufiksem danego napisu nazwiemy dowolny jego końcowy fragment.
W szczególności, pusty napis jest zarówno prefiksem jak i sufiksem dowolnego napisu.
Dwa napisy nazywamy cyklicznie równoważnymi, jeżeli jeden z nich można uzyskać
z drugiego, przestawiając pewien jego sufiks z końca napisu na początek.
Dla przykładu, napisy
i
są równoważne cyklicznie, a napisy
i
nie są.
W szczególności, każdy napis jest sam sobie cyklicznie równoważny.
Dany jest napis
złożony z
liter.
Szukamy jego prefiksu
i sufiksu
, obu tej samej długości, takich że:
-
i
są sobie równoważne cyklicznie,
-
długość
i
nie przekracza
(czyli prefiks
i sufiks
nie zachodzą na siebie w
), oraz
-
długość
i
jest jak największa.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(
), oznaczającą długość danego napisu
.
Drugi wiersz wejścia zawiera napis
składający się z
małych liter alfabetu angielskiego.
W testach wartych 30% punktów zachodzi dodatkowy warunek
.
W testach wartych 50% punktów zachodzi dodatkowy warunek
.
Wyjście
Twój program powinien wypisać w pierwszym i jedynym wierszu standardowego wyjścia jedną liczbę całkowitą,
równą długości szukanego prefiksu
i sufiksu
.
Przykład
Dla danych wejściowych:
15
ababbabababbaab
poprawną odpowiedzią jest:
6
Autor zadania: Jacek Tomasiewicz.